#pragma once

#include<iostream>
#include<vector>
#include<stack>
using namespace std;
//三数取中，找left mid right 当中最大的数的下标
int MidIndex(std::vector<int>& nums, int left, int right)
{
    int mid = left + (right-left)/2;
    if(nums[mid] > nums[left])
    {
        if(nums[left] > nums[right])
        {
            return left;
        }
        else if(nums[right] > nums[mid])
        {
            return mid;
        }
        else
        {
            return right;
        }
    }
    else//left >= mid
    {
        if(nums[mid] > nums[right])
        {
            return mid;
        }
        else if(nums[right] > nums[left])
        {
            return left;
        }
        else{
            return right;
        }
    }
}
//hoare版本快排
int hoareSort(std::vector<int>& nums, int left, int right)
{
    int mid = MidIndex(nums, left, right);
    std::swap(nums[left], nums[mid]);
    int keyi = left;

    while(left<right)
    {
        while(left<right && nums[right] >= nums[keyi])
        {
            right--;
        }
        while(left<right && nums[left] <= nums[keyi])
        {
            left++;
        }
        std::swap(nums[left], nums[right]);
    }
    std::swap(nums[left], nums[keyi]);
    return left;
}
//挖坑法
int PartSort(std::vector<int>& nums, int left, int right)
{
    int mid = MidIndex(nums, left, right);
    std::swap(nums[left], nums[mid]);
    int tmp = nums[left];
    while(left < right)
    {
        //右边找小的放到左边
        while(left<right && nums[right] >= tmp)
        {
            right--;
        }
        nums[left] = nums[right];
        //左边找大的放到右边
        while(left<right && nums[left] <= tmp)
        {
            left++;
        }
        nums[right] = nums[left];
    }
    nums[left] = tmp;
    return left;
}

void quickSort(std::vector<int>& nums, int begin, int end)
{
    if(begin >= end)
    {
        return;
    }
    int mid = hoareSort(nums, begin, end);
    quickSort(nums, begin, mid-1);
    quickSort(nums, mid+1, end);
}

//迭代版本的快排
void quickSortNonR(std::vector<int>& nums, int begin, int end)
{
    //将左右索引放入栈里,然后迭代取出排序这一段序列
    std::stack<int> st;
    st.push(begin);
    st.push(end);

    while(!st.empty())
    {
        int right = st.top();
        st.pop();
        int left = st.top();
        st.pop();

        int keyi = PartSort(nums, left, right);
        if(left < keyi-1)
        {
            st.push(left);
            st.push(keyi-1);
        }
        if(keyi+1 < right)
        {
            st.push(keyi+1);
            st.push(right);
        }
    }

    cout<<"quick NonR end..."<<endl;
}

//向下调整算法
void AdjustDown(std::vector<int>& nums, int parent, int n)//n代表最大下标
{
    int child = parent*2+1;
    while(child < n)
    {
        if(child+1 < n && nums[child] < nums[child+1])
        {
            child++;
        }
        if(nums[parent] < nums[child])
        {
            std::swap(nums[parent], nums[child]);
            parent = child;
            child = parent*2+1;
        }
        else
        {
            //孩子比父亲大，无需处理，调整完成，整个数已经是大堆
            break;
        }
    }
}
int HeapSort(std::vector<int>& nums)
{
    //先建堆,以升序为例,建大堆
    int last = nums.size()-1;
    //从last的父节点开始调整堆
    for(int i=(last-1)/2; i>=0; i--)
    {
        AdjustDown(nums, i, nums.size());
    }

    for(int i=last; i>0; i--)
    {
        std::swap(nums[0], nums[i]);
        AdjustDown(nums, 0, i);
    }

}


//归并排序
void MergeCore(vector<int>& nums, int begin1, int end1, int begin2, int end2)
{
    vector<int> tmp(nums.size(), 0);
    int i=begin1;
    int j=begin1;
    while(begin1<=end1 && begin2<=end2)
    {
        if(nums[begin1] <= nums[begin2])
        {
            tmp[i++] = nums[begin1++];
        }
        else
        {
            tmp[i++] = nums[begin2++];
        }
    }

    while (begin1 <= end1)
		tmp[i++] = nums[begin1++];
	while (begin2 <= end2)
		tmp[i++] = nums[begin2++];
    for(; j<= end2; j++)
    {
        nums[j] = tmp[j];
    }
}
void MergeSort(vector<int>& nums, int start, int end)
{
    if(start >= end)
    {
        return;
    }
    int mid = start + (end - start)/2;
    MergeSort(nums, start, mid);
    MergeSort(nums, mid+1, end);

    //对每个区间进行排序
    MergeCore(nums, start, mid, mid+1, end);
}

//非递归实现归并排序
void MergeNonR(vector<int>& nums)
{
    int gap = 1;//每次一个区间里排序gap个数字
    int n = nums.size();
    while(gap < n)
    {
        for(int i=0; i<n; i+=gap*2)
        {
            int begin1 = i, end1 = i+gap-1;//第一个区间
            int begin2 = i+gap, end2 = i+2*gap-1;//第二个区间
            //第二个区间不存在或者第一个区间凑不齐,直接跳出本次排序
            if(begin2 >= n)
                break;
            //如果第二个区间凑不齐,修改区间结尾
            if(end2 >= n)
            {
                end2 = n-1;
            }
            MergeCore(nums, begin1, end1, begin2, end2);
        }
        gap *= 2;
    }
    cout<<"Merge NonR end..."<<endl;
}